import com.sun.media.sound.FFT;

import java.util.Arrays;

/**
 * @ClassName KP11_binarySearch
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/10/9 9:18
 */


public class KP12_binarySearchMostLeftIndex {

    /**
     * 方法一
     * 二分查找算法
     * 有序数组中找到=num最左的位置
     *
     * @param sortedArray
     * @param num
     * @return
     */
    public static int binarySearchMostLeftIndex(int[] sortedArray, int num) {
        if (sortedArray == null || sortedArray.length == 0) {
            return -1;
        }
        int L = 0;
        int R = sortedArray.length - 1;
        int ans = -1;
        while (L <= R) {
            int mid = (L + R) / 2;
            /**
             * 找最左边的就是把之前判断右边的合并，因为我要往左找，找到了就把右边的扔了
             * if (sortedArray[mid] == num) {
             *      ans = mid;
             *      break;
             *  } else if (sortedArray[mid] >= num) {
             *      R = mid - 1;
             *  }
             */
            if (sortedArray[mid] >= num) {
                ans = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return ans;
    }


    /**
     * 方法二
     * 二分查找算法
     * 有序数组中找到=num最左的位置
     * 存在问题，当连续几个相同的数字在一起时R=mid会使程序进入死循环
     *
     * @param sortedArray
     * @param num
     * @return
     */
    public static int binarySearch(int[] sortedArray, int num) {
        if (sortedArray == null || sortedArray.length == 0) {
            return -1;
        }
        int L = 0;
        int R = sortedArray.length - 1;
        int ans = -1;
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (sortedArray[mid] == num) {
                // 取=num最左的位置时R下标的变动
                R = mid;
                ans = R;
            } else if (sortedArray[mid] > num) {
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return ans = sortedArray[L] == num ? sortedArray[L] : sortedArray[R];
    }

    /**
     * 检查查找算法是否正确
     */
    public static int testFindIndex(int[] rands, int randNum) {
        for (int i = 0; i < rands.length; i++) {
            if (rands[i] == randNum) return i;
        }
        return -1;
    }

    /**
     * 生成任意规模的抽样测试数组
     *
     * @param maxLen
     * @param maxValue
     * @return
     */
    public static int[] randomArray(int maxLen, int maxValue) {
        int[] rands = new int[(int) (Math.random() * (maxLen + 1))];
        for (int i = 0; i < rands.length; i++) {
            rands[i] = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
        }
        return rands;
    }

    /**
     * 生成测试查找函数
     */
    public static void testFind() {
        int maxLen = 10;
        int maxValue = 1000;
        int maxtimes = 100000;
        for (int i = 0; i < maxtimes; i++) {
            int[] rands = randomArray(maxLen, maxValue);
            Arrays.sort(rands);

            if (rands == null || rands.length == 0) {
                System.out.println("数组为null或为空");
                continue;
            }
            // 随机生成的数一般查找到的概率不大
            int randNum = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
            boolean flag = true;
            int index = -1;
            if ((index = binarySearch(rands, randNum)) != testFindIndex(rands, randNum)) {
                System.out.println("代码出现bug");
                System.out.println(Arrays.toString(rands));
                System.out.println("查找的数为：" + randNum + " 返回的下标为：" + index);
                flag = false;
                break;
            }
            System.out.println(flag ? "Success!!!" : "Fatal error!!!");
        }
    }

    public static void main(String[] args) {
        // 测试testFind函数
        //testFind();

        // 测试testFind函数
        //testFind();

        int[] array = {12, 23, 34, 45, 56, 67, 78, 78, 78, 89};
        binarySearch(array, 78);
    }
}
